package com.gxc.stack;

import java.util.Stack;

/**
 * 实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
 * 要求:
 * 1.pop、push、getMin 操作的时间复杂度都是0(1);
 * 2.设计的栈类型可以使用现成的栈结构
 *
 * 解法：
 * 1.设计两个栈，
 * 一个普通栈记录所有元素，
 * 另一个最小栈，由于栈的先进后出特性，按栈元素的进入顺序，维护一个特殊栈，当进入元素比最小栈栈顶的元素小时，元素同时也进入最小栈
 */
public class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    /**
     * 当弹出的元素是最小元素时，从最小栈中同时把元素弹出
     * @return
     */
    public Integer pop() {
        Integer pop = stack.pop();
        //当弹出的元素是最小元素时，从最小栈中同时把元素弹出
        minStack.pop();
        return pop;
    }

    /**
     * 添加新元素时
     * 1.如果最小栈为空，则直接添加
     * 2.当前元素和最小栈栈顶元素比较，小等于则加入最小栈
     * @param num
     */
    public void push(Integer num) {
        stack.push(num);
        if (minStack.isEmpty()) minStack.push(num);
        else minStack.push(Math.min(num, minStack.peek()));
    }

    public Integer getMin() {
        if (minStack.isEmpty()) {
            return -1;
        }
        return minStack.peek();
    }

    public int top() {
        return stack.peek();
    }

    private Stack<Long> stack2;
    private long minVal;

    public MinStack(int a) {
        stack = new Stack<>();
    }

    public void push2(int val) {
        if (stack2.isEmpty()) {
            stack2.push(0L);
            minVal = val;
        } else {
            long diff = (long) val - minVal;
            stack2.push(diff);
            if (diff < 0) {
                minVal = val;
            }
        }
    }

    public void pop2() {
        if (stack2.isEmpty()) return;
        long diff = stack.pop();
        if (diff < 0) {
            minVal = minVal - diff;
        }
    }

    public int top2() {
        long diff = stack.peek();
        return diff < 0 ? (int) minVal : (int) (minVal + diff);
    }

    public int getMin2() {
        return (int) minVal;
    }
}
